package com.barry.algorithm.sort;

/**
 * 类功能描述：选择排序算法
 *
 * @author WangXueXing create at 19-9-4 下午4:42
 * @version 1.0.0
 */
public class SelectionSort {
    /**
     * 选择排序算法
     * 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
     * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     * 以此类推，直到所有元素均排序完毕。
     * 基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列前面，直到全部记录排序完毕。
     *
     * @param a 被排序的数组
     * 最坏情况：O（n2） ，最好情况：O（n2）
     */
    public static void selectSort(int[] a) {
        int len = a.length;
        for (int i = 0; i < len; i++) {
            int min = a[i]; //先把每一趟最小值暂定为nums[i]
            int index = i; //记录最小值所在的索引值
            for (int j = i + 1; j < len; j++) { //开始一趟比较：从i+1位置到数组末尾比较，找出最小值并记录位置
                if (a[j] < min) {
                    min = a[j];
                    index = j;
                }
            }
            //将nums[i]和最小值交换
            a[index] = a[i];
            a[i] = min;
        }
        System.out.println("选择排序：");
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println("");
    }

    /**
     * 堆排序算法(max堆)
     * 介绍：
     * 堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。
     *
     * 二叉堆具有以下性质：
     * 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
     * 每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。
     *
     * 步骤：
     * 构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。
     * 堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
     *
     * 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。
     * @param nums 被排序的数组
     * 时间复杂度 O（nlogn）
     * 要先构建最大堆，然后循环删除堆的根节点上的最大值，并将它移到堆末尾，并将堆长度减一，再开始下一次的删除根节点
     */
    public static void heapSort(int[] nums){
        int len = nums.length;
        //构建最大堆
        for(int i=len/2;i>=0;i--){
            percDown(nums,i,len);
        }
        //循环，每次把根节点和最后一个节点调换位置
        for(int i=len-1;i>=1;i--){
            //Swap(nums[0],nums[i])交换nums[0]和nums[i]
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            percDown(nums,0,i);
        }

        System.out.println("堆排序：");
        for (int k : nums) {
            System.out.print(k+" ");
        }
    }
    /**
     * 堆调整，使其生成最大堆
     * @param a
     * @param i
     * @param size
     */
    public static void percDown(int[] a,int i,int size){
        int left = 2*i+1;
        int right = 2*i+2;
        int max = i;
        if(left < size && a[left] > a[max]){
            max = left;
        }
        if(right < size && a[right] > a[max]){
            max = right;
        }
        if(max != i){
            int temp = a[i];
            a[i] = a[max];
            a[max] = temp;
            percDown(a,max,size);
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{2,3,6,4,7,5,1};
        selectSort(a);
        heapSort(a);
    }
}
